package com.company.gxcpc2020;

import java.util.Arrays;
import java.util.Scanner;

public class GxcpcI {

	public static int[] prime;
	public static boolean[] flags;
	public static int[][] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt(), m = sc.nextInt();
			prime = new int[m + 1];
			flags = new boolean[m + 1];
			susu(m);
			System.out.println(Arrays.toString(prime));
			dp = new int[prime[0] + 1][n + 1];
			for (int i = 0; i < prime[0]; i++) {
				dp[i + 1][prime[i + 1]] = 1;
			}
			for (int i = 1; i < dp.length; i++) {
				for (int j = 0; j < dp[i].length; j++) {
					int k = prime[i];
					if (k > j) {
						continue;
					}
					if (dp[i - 1][j - k] != 0) {
						dp[i][j] = dp[i - 1][j - k] + dp[i][j];
					}
					dp[i][j] += dp[i - 1][j];
				}
			}
			System.out.println(Arrays.deepToString(dp));
			System.out.println(dp[prime[0]][n] % 2);
		}
	}

	/**
	 * 欧式筛法
	 * 
	 * @param n
	 */
	public static void susu(int n) {

		for (int i = 2; i <= n; i++) {
			if (flags[i])
				continue;
			prime[++prime[0]] = i;
			for (int j = i; j <= n / i; j++)
				flags[i * j] = true;
		}
	}
}
